package com.yubest;

/**
 * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
 *
 *
 *
 * 示例 1：[图片] img/0938_1.jpg
 *
 *
 * 输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
 * 输出：32
 * 示例 2：[图片] img/0938_2.jpg
 *
 *
 * 输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
 * 输出：23
 *
 *
 * 提示：
 *
 * 树中节点数目在范围 [1, 2 * 10^4] 内
 * 1 <= Node.val <= 10^5
 * 1 <= low <= high <= 10^5
 * 所有 Node.val 互不相同
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/range-sum-of-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/12 15:42
 */
public class P0938 {
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution938 {

    private int total = 0;

    /**
     * 思路：因为中序遍历是递增序列，所以问题转换为取中序遍历中范围在 low 和 hight 之前的数累加即可
     * @param root
     * @param low
     * @param high
     * @return
     */
    public int rangeSumBST(TreeNode root, int low, int high) {
        dfs(root, low, high);
        return total;
    }

    private void dfs(TreeNode root, int low, int high) {
        if (null == root) {
            return;
        }
        dfs(root.left, low, high);
        if (root.val >= low && root.val <= high) {
            total += root.val;
        }
        dfs(root.right, low, high);
    }

}
